import { Sort } from "../public/Sort"
import { DefaultCompare, ICompareFunction, CompareEnum } from "../public/Utils"
import { InsertionSort } from "../InsertionSort/InsertionSort"
/**
 * 桶排序
 * 桶排序也是一种分布式排序算法，它将元素分为不同的桶，再使用一个简单的排序算法，
 * 例如插入排序，来对每个桶进行排序，最后，它将所有的桶合并为结果数组。
 * **/
export class BucketSort<T> extends Sort<T> {
    constructor(array: Array<T> = [], compareFun: ICompareFunction = new DefaultCompare()) {
        super(array, compareFun)
    }
    sort(array: Array<T> = this.array, bucketSize = 5): Array<T> {
        const { length } = array
        if (length < 2) {
            return array
        }
        //创建桶，对桶进行排序
        return this.sortBuckets(<Array<Array<T>>>this.createBuckets(array, bucketSize))
    }

    //创建桶
    private createBuckets = (array: Array<T>, bucketSize: number): Array<Array<T>> => {
        //计算数组最大值与最小值
        let minValue: number = <number>array.reduce((a, b) => {
            return a < b ? a : b
        })
        let maxValue: number = <number>array.reduce((a, b) => {
            return a < b ? b : a
        })

        //计算需要的桶数量，公式为：数组最大值与最小值的差值与桶大小进行除法运算后+1
        const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1
        //用于存放桶的二维数组
        const buckets: Array<Array<T>> = new Array<Array<T>>(bucketCount)

        // 计算出桶数量后，初始化每个桶
        for (let i = 0; i < bucketCount; i++) {
            buckets[i] = [];
        }

        //遍历数组，将每个元素分布到桶中
        for (let i = 0; i < array.length; i++) {
            //计算需要将元素放到哪个桶中，公式为：当前遍历到的元素值与数组的最小值的差值与桶大小进行除法运算
            const bucketIndex: number = Math.floor((<number>array[i] - minValue) / bucketSize)

            //将元素放进合适的桶中
            buckets[bucketIndex] && buckets[bucketIndex].push(array[i])
        }
        //将桶返回
        return buckets;
    }


    //对每个桶进行排序
    private sortBuckets(buckets: Array<Array<T>>): Array<T> {
        const sortedArray: Array<T> = new Array()
        for (let i = 0; i < buckets.length; i++) {
            if (buckets[i] != null) {
                //调用插入排序
                const insertionSort: Sort<T> = new InsertionSort<T>(buckets[i])
                insertionSort.sort()
                //将排序好的桶取出来，放进sortedArray中
                sortedArray.push(...buckets[i])
            }
        }
        return sortedArray
    }
}

const BucketSortTest = (): void => {
    const array = [33,23, 44, 67, 15, 54,88]
    const bucketSort: Sort<Number> = new BucketSort<Number>(array)
    console.log(bucketSort.sort());
}
BucketSortTest()